package sword.chapter6Stack;

import java.util.Stack;

/**
 * 小行星碰撞
 *
 * 消除 循环出栈
 * 入栈
 * 出栈
 *
 * @author K
 * @date 2021/12/3 17:24
 */
public class S37AsteroidCollision {
    public static int[] s37(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();
        for (int asteroid : asteroids) {
            // 消除 1. 栈顶为正数，2. 当前asteroid为负数，且栈顶数小于asteroid的绝对值
            while (!stack.empty() && stack.peek() > 0 && stack.peek() < -asteroid) {
                stack.pop();
            }

            if (stack.empty() || stack.peek() < 0 || asteroid > 0) {
                // 入栈逻辑与 1. stack.empty() 2. stack.peek()<0 3.asteroid > 0
                stack.push(asteroid);
            } else if (!stack.empty() && stack.peek() > 0 && stack.peek() == -asteroid) {
                // 等值相撞 栈顶为正数 当前值为负数且绝对值等于栈顶数。栈顶出栈 当前值不入栈
                stack.pop();
            }

            // 相撞 栈顶为正数 当前值为负数且绝对值小于栈顶数，被消除。当前值不入栈
        }
        return stack.stream().mapToInt(x -> x).toArray();
    }

    public static void main(String[] args) {
        int[] ints = {4, 5, -6, 4, 8, -5};
        int[] result = s37(ints);
        System.out.println();
    }

}
